package com.zjsru.plan2023.oneday;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: cookLee
 * @Date: 2023-09-10
 * 课程表 II
 */
public class FindOrder {

    /**
     * 输入：numCourses = 2, prerequisites = [[1,0]]
     * 输出：[0,1]
     * 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
     * \
     * 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
     * 输出：[0,2,1,3]
     * 解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     * 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
     * \
     * 输入：numCourses = 1, prerequisites = []
     * 输出：[0]
     */
    public static void main(String[] args) {
        FindOrder findOrder = new FindOrder();
        int numCourses = 4;
        int[][] prerequisites = new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        System.out.println(Arrays.toString(findOrder.findOrder(numCourses, prerequisites)));
    }

    /**
     * 存储有向图
     */
    List<List<Integer>> edges;
    /**
     * 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
     */
    int[] visited;
    /**
     * 用数组来模拟栈，下标 n-1 为栈底，0 为栈顶
     */
    int[] result;
    /**
     * 判断有向图中是否有环
     */
    boolean valid = true;
    /**
     * 栈下标
     */
    int index;

    /**
     * 课程表
     *
     * @param numCourses
     * @param prerequisites
     * @return {@link int[]}
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        result = new int[numCourses];
        index = numCourses - 1;
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        //遍历找到一个为搜索的节点， dfs
        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {
                this.dfs(i);
            }
        }
        if (!valid) {
            return new int[0];
        }
        //没有环就拓扑排序
        return result;
    }

    /**
     * 深度优先搜索
     *
     * @param i
     */
    private void dfs(int i) {
        //节点标记为 搜索中
        visited[i] = 1;
        //搜索相邻节点
        //发现有环 停止搜索
        for (int v : edges.get(i)) {
            //存在 未搜索 搜索相邻节点
            if (visited[v] == 0) {
                this.dfs(v);
                if (!valid) {
                    return;
                }
            }
            //如果 搜索中 找到了环
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        //节点标记为 已完成
        visited[i] = 2;
        //将节点入栈
        result[index--] = i;
    }

}
